Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

  1. public class Solution {
  2.   public int maxProfit(int k, int[] prices) {
  3.     int n = prices.length;
  5.     if (k >= n) {
  6.         return solveMaxProfit(prices);
  7.     }
  9.     // The local array tracks maximum profit of j transactions & the last transaction is on ith day. 
  10.     // The global array tracks the maximum profit of j transactions until ith day.
  11.     int[][] local = new int[n][k + 1];
  12.     int[][] global = new int[n][k + 1];
  14.     for (int i = 1; i < n; i++) {
  15.       int diff = prices[i] - prices[i - 1];
  17.       for (int j = 1; j <= k; j++) {
  18.         local[i][j] = Math.max(
  19.           global[i - 1][j - 1] + Math.max(diff, 0),
  20.           local[i - 1][j] + diff
  21.         );
  23.         global[i][j] = Math.max(global[i - 1][j], local[i][j]);
  24.       }
  25.     }
  27.     return global[n - 1][k];
  28.   }
  30.   private int solveMaxProfit(int[] prices) {
  31.     int profit = 0;
  33.     for (int i = 1; i < prices.length; i++) {
  34.       // as long as there is a price gap, we gain a profit.
  35.       if (prices[i] > prices[i - 1]) {
  36.         profit += prices[i] - prices[i - 1];
  37.       }
  38.     }
  40.     return profit;
  41.   }
  42. }